package pro.softzhang.algo.lc2500;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 2542. 最大子序列的分数
 * https://leetcode.cn/problems/maximum-subsequence-score
 */
public class LC2542_MaximumSubsequenceScore {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public long maxScore(int[] nums1, int[] nums2, int k) {
            int n = nums1.length;
            Integer[] ids = new Integer[n];
            for (int i = 0; i < n; i++) {
                ids[i] = i;
            }
            // 对下标排序，不影响原数组的顺序
            Arrays.sort(ids, (i, j) -> nums2[j] - nums2[i]);

            PriorityQueue<Integer> pq = new PriorityQueue<>();
            long sum = 0;
            for (int i = 0; i < k; i++) {
                sum += nums1[ids[i]];
                pq.offer(nums1[ids[i]]);
            }

            long ans = sum * nums2[ids[k - 1]];
            for (int i = k; i < n; i++) {
                int x = nums1[ids[i]];
                if (x > pq.peek()) {
                    sum += x - pq.poll();
                    pq.offer(x);
                    ans = Math.max(ans, sum * nums2[ids[i]]);
                }
            }
            return ans;
        }
    }
}
